#!/usr/bin/env python3

"""
Given a linked list, swap every two adjacent nodes and return its head.

Given 1-> 2-> 3-> 4, you should return the list as 2-> 1 -> 4 -> 3
"""

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

    def show(self):
        print(str(self.val))
        if self.next:
            self.next.show()


class Solution:
    def swap_pairs(self, head):
        if head is None or head.next is None:
            return head
        head_second = head.next
        head_third = head_second.next if head_second else None
        head_second.next = head
        head.next = self.swap_pairs(head_third)
        return head_second

if __name__ == '__main__':
    head = None
    current = None
    for node in [1, 2, 3, 4]:
        if head is None:
            head = current = ListNode(node)
        else:
            current.next = ListNode(node)
            current = current.next

    head.show()
    solution = Solution()
    result = solution.swap_pairs(head)
    result.show()
            
